- Title
- Efficient intelligent backtracking using linear programming
- Creator
- Davey, Bruce; Boland, Natashia; Stuckey, Peter J.
- Relation
- INFORMS Journal on Computing Vol. 14, Issue 4, p. 373-386
- Publisher Link
- http://dx.doi.org/10.1287/ijoc.14.4.373.2823
- Publisher
- Institute for Operations Research and the Management Sciences (INFORMS)
- Resource Type
- journal article
- Date
- 2002
- Description
- Intelligent backtracking is a technique used in constraint programming for reducing search in solving combinatorial feasibility problems. The technique uses information derived from small sets of infeasible constraints discovered in one part of the search space to avoid searching other, similar, regions. It is often able to reduce the size of the search space significantly. For many problems, however, the computational effort required to achieve this reduction in search space is prohibitive. We introduce an algorithm that uses intelligent backtracking inside a linear-programming based branch-and-bound framework. We show that minimal infeasible sets can immediately be deduced from the dual extreme ray associated with the infeasible linear program. This allows us to obtain the reduction in search space associated with intelligent backtracking, without paying the large computational cost. We show the implementation of our intelligent backtracking approach as a branch-and-cut algorithm, and present computational results.
- Subject
- integer programming; algorithms; branch and bound; cutting planes
- Identifier
- http://hdl.handle.net/1959.13/939500
- Identifier
- uon:12824
- Identifier
- ISSN:1526-5528
- Language
- eng
- Reviewed
- Hits: 2092
- Visitors: 2333
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|